package com.mccken.practice.top100.Top_30$.Top_37;

import java.util.LinkedList;

import com.mccken.practice.top100.TreeNode;

/**
 * https://leetcode.cn/problems/symmetric-tree/?envType=study-plan-v2&envId=top-100-liked
 *
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2024-04-01 22:08
 **/
public class IsSymmetric_101 {

	public static void main(String[] args) {
		IsSymmetric_101 test = new IsSymmetric_101();
	}

	public boolean isSymmetric(TreeNode root) {
		if (root == null || (root.left == null&& root.right == null)) {
			return true;
		}
		
		// 用队列保存节点
		LinkedList<TreeNode> queue = new LinkedList<>();
		// 将根节点的左右孩子放到队列中
		queue.add(root.left);
		queue.add(root.right);
		
		while (!queue.isEmpty()) {
			// 从队列中取出两个节点，再比较这两个节点
			TreeNode left = queue.pop();
			TreeNode right = queue.pop();
			
			// 如果这两个节点都是空，就继续循环，有一个不为空就直接返回false
			if (left == null && right == null) {
				continue;
			}
			
			if (left == null || right == null) {
				return false;	
			}
			
			if (left.val != right.val) {
				return false;
			}
			
			queue.add(right.right);
			queue.add(left.left);
			
			queue.add(right.left);
			queue.add(left.right);
		}
		return true;
	}
	// 递归实现
	public boolean isSymmetric1(TreeNode root) {
		if (root == null) {
			return true;
		}
		// 调用递归函数，比较左节点，右节点
		return dfs(root.left, root.right);
	}

	private boolean dfs(TreeNode left, TreeNode right) {
		//  todo 终止条件
		if (left == null && right == null) {
			return true;
		}

		if (left == null || right == null) {
			return false;
		}

		if (left.val != right.val) {
			return false;
		}

		return dfs(left.left, right.right) && dfs(left.right, right.left);
	}
}
